package com.jankins.pat;

import java.util.Map;
import java.util.Scanner;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;

public class RomeRoads {
    private final int INFINITY = Integer.MAX_VALUE;

    private Map<String, Integer> st;
    private int[] happies;
    private Graph graph;

    private class Graph {
        private int V;
        private int E;
        private int[][] adj;

        public Graph(int V, int E) {
            this.V = V;
            this.E = E;
            this.adj = new int[V][V];
        }

        public void addEdge(int v, int w, int weight) {
            adj[v][w] = weight;
            adj[w][v] = weight;
        }

        public Set<Integer> neighbors(int v) {
            Set<Integer> neighbors = new HashSet<>();

            for(int w = 0; w < V; w++) {
                if(adj[v][w] != 0)
                    neighbors.add(w);
            }
            return neighbors;
        }   

        public int weight(int v, int w) {
            return adj[v][w];
        }
    }

    public RomeRoads(Scanner in) {
        int V = in.nextInt();
        int E = in.nextInt();

        graph = new Graph(V, E);

        // initial the graph symbol table
        st = new HashMap<>();
        happies = new int[V];
        String start = in.next();
        st.put(start, 0);
        happies[0] = 0;
        for(int i = 1; i < V; i++) {
            String name = in.next();
            int happy = in.nextInt();
            st.put(name, i);
            happies[i] = happy;
        }

        // initial the edges
        for(int j = 0; j < E; j++) {
            String first = in.next();
            String second = in.next();
            int weight = in.nextInt();
            graph.addEdge(indexOf(first), indexOf(second), weight);
        }
    }

    private int indexOf(String name) {
        return st.get(name);
    }

    private String nameOf(int index) {
        for(String name : st.keySet()) {
            if(st.get(name) == index)
                return name;
        }
        return null;  
    }

    // the collections for all cost-least paths
    private List<List<Integer>> paths; 

    public void searchPaths(String dst) {
        int target = this.indexOf(dst);

        paths = new ArrayList<>();
        router = new ArrayList<>();

        dfs(0, target);

    }

    private List<Integer> router;
    private int costs = INFINITY;           // the costs of the current path
    private int dist = 0;

    // using the backtracking to get the all shortest paths to destination 
    private void dfs(int current, int target) {
        router.add(current);  // target is arrival

        if(current == target) {
            List<Integer> path = new ArrayList<>(router);

            if(dist < costs) {
                paths.clear();
                paths.add(path);
                costs = dist;
            } else if(dist == costs) {
                paths.add(path);
            }

            return;
        }

        for (int w : graph.neighbors(current)) {
            // boundary condition
            if(!router.contains(w)) {
                dist += graph.weight(current, w);
                dfs(w, target);
                // backtracking
                dist -= graph.weight(current, w);
                router.remove((Integer) w);
            }
        }
    }

    public void printSP() {
        int result = 0;
        int hp = 0;
        int avg = 0;

        for(int i = 0; i < paths.size(); i++) {
            int hpy = 0;
            for(Integer v : paths.get(i)) {
                hpy += happies[v];
            }

            int avgs = hpy / (paths.get(i).size() - 1);

            if(hp < hpy) {
                result = i;
                hp = hpy;
            } else if(hp == hpy && avg < avgs) {
                result = i;
                avg = avgs;
            }
        }

        String numeric = String.format("%d %d %d %d", 
                                        paths.size(), costs, hp, avg);

        System.out.println(numeric);

        for(int i = 0; i < paths.get(result).size(); i++) {
            System.out.print(nameOf(paths.get(result).get(i)));
            if(i < paths.get(result).size() - 1) 
                System.out.print("->");
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while(in.hasNextLine()) {
            RomeRoads romeRoads = new RomeRoads(in);

            romeRoads.searchPaths("ROM");
            romeRoads.printSP();
        }
    }
}
